import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 1743. 从相邻元素对还原数组
 * <a href="https://leetcode.cn/problems/restore-the-array-from-adjacent-pairs/description/">...</a>
 * User: DELL
 * Date: 2023-10-12
 * Time: 23:23
 */
public class Solution {
    /**
     * 解题思路: (哈希+异或寻找出现奇数次的数字)
     * 通过题目的描述,我们可以很容易的得到,在 adjacentPairs 数组中出现一次的两个数字,
     * 应该分别为数组的开始元素和结束元素,那么如何快速且高效的将他们找出来呢,这里就用到异或.
     * 首先先将 adjacentPairs 数组中的所有元素和 temp = 0 进行异或,之后取 temp 中为 1
     * 的比特位,根据这个比特位将原 adjacentPairs 数组中的元素分为两组,每组单独进行异或,即
     * 可得到两个均出现一次的数字.
     * 接下来需要考虑的就是如何处理这些相邻元素,使得能够快速的恢复出原数组.
     * 这里我想到的是使用 HashMap,其中 key 为元素值, value 为其在原数组中左右元素的值之和,
     * 那么在找到第一个元素后,根据第一个元素就很容易将原数组恢复出来了.
     * 即得到第一个元素后,查找 hashMap 后就可以得到其下一个元素值,之后根据第二个元素值,就可
     * 以查找第二个元素的左右元素值之和,再减去第一个元素值即可得到第三个元素的值,以此类推,即可
     * 恢复数组.
     *
     * @param adjacentPairs
     * @return
     */
    public int[] restoreArray(int[][] adjacentPairs) {
        int temp = 0;
        int len = adjacentPairs.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            temp ^= adjacentPairs[i][0];
            temp ^= adjacentPairs[i][1];
            hashMap.put(adjacentPairs[i][0], hashMap.getOrDefault(adjacentPairs[i][0], 0) + adjacentPairs[i][1]);
            hashMap.put(adjacentPairs[i][1], hashMap.getOrDefault(adjacentPairs[i][1], 0) + adjacentPairs[i][0]);
        }
        // 寻找最小的为 1 的比特位
        int smallBit = 0;
        while ((temp & (1 << smallBit)) == 0) {
            smallBit++;
        }
        // 根据最小的比特位将原来的元素分两组分别进行异或
        int begin = 0;
        int end = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 2; j++) {
                if ((adjacentPairs[i][j] & (1 << smallBit)) == 0) {
                    begin ^= adjacentPairs[i][j];
                } else {
                    end ^= adjacentPairs[i][j];
                }
            }
        }
        // 根据 hashMap 和起始终点元素,恢复原数组
        int[] res = new int[len + 1];
        // 这里先对数组进行适当初始化,方便后面循环
        res[0] = begin;
        res[1] = hashMap.get(begin);
        res[len] = end;
        for (int i = 1; i < len; i++) {
            int sum = hashMap.get(res[i]);
            res[i + 1] = sum - res[i - 1];
        }
        return res;
    }
}